class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
    }
}
/**
 * https://leetcode-cn.com/problems/binary-tree-inorder-traversal/submissions/
 * 二叉搜索树的中序遍历
 * @param root 
 */
const inorderTraversal = (root: TreeNode | null): number[] => {
    // 二叉树为空
    if (root === null) return []

    const arr: number[] = []

    /**
     * 获取n的前驱节点
     * @param n 
     */
    const getAced = (n: TreeNode) => {
        let left = n.left;
        while (left !== null && left.right !== null && left.right !== n) {
            left = left.right;
        }
        return left;
    }
    let p = root;
    while (p !== null) {
        if (p.left !== null) {
            // 左子树不为空, 找到前驱节点
            const aced: TreeNode = getAced(p)!;
            // 右边为空
            if (aced.right == null) {
                aced.right = p;

                // 继续往左子树遍历
                p = p.left;
            } else if (aced.right === p) {
                arr.push(p.val)

                // 恢复二叉树原状
                aced.right = null;

                // 开始找右子树
                p = p.right!;
            }

        } else {
            // 左子树为空, 指向右子树, 访问左子树
            arr.push(p.val);
            p = p.right!;
        }
    }
    return arr;
};

const inorderTraversal2 = (root: TreeNode | null): number[] => {
    // 二叉树为空
    if (root === null) return []

    const arr: number[] = []

    // 递归
    const inorder = (n: TreeNode | null) => {
        if (n === null) return;
        inorder(n.left)
        arr.push(n.val);
        inorder(n.right);
    }
    inorder(root);
    return arr;
};

const root = new TreeNode(1, null, new TreeNode(2, new TreeNode(3, null, null)))
inorderTraversal(root)

// new Promise(res => res(new Promise(res => res(1)))).then(res => console.log(res))